package com.arron.algorithm.leetcodetop100.优先级队列;

public class MaxPQ {

    private Integer[] que;

    private int size;



    public MaxPQ(int capity){

        que = new Integer[capity+1];

    }


    public int getMax(){
        return size <1? -1: que[1];
    }

    public int getParent(int k){
        return k >> 1;
    }

    public int getLeftChild(int k){
        return k*2;
    }
    public int getRightChild(int k){
        return k*2+1;
    }


    public void insert(int v){
        size++;

        que[size] = v;

        //将元素上浮到正确位置
        swimUp(size);

    }

    public int delMax(){

        if (size <1){

            return -1;
        }

        int max =  que[1];

        swap(1,size);
        que[size] =null;
        size--;
        sinkDown(1);
        return max;
    }

    private void swimUp(int k) {
        int p =k;
        while (k>1 && que[getParent(k)] < que[k]){
            k = k>>1;
        }
        swap(p,k);
    }

    public void sinkDown(int k){

        while (getLeftChild(k) <= size){

            //先假设左节点为最大
            int maxIndex = getLeftChild(k);

            if (getRightChild(k) <= size && que[getRightChild(k)] > que[maxIndex]){
                maxIndex = getRightChild(k);
            }

            if (que[k] < que[maxIndex]){

                //需要交换节点值
                swap(maxIndex,k);
            }
            k = maxIndex;

        }


    }

    private void swap(int maxIndex, int k) {
        int temp = que[k];
        que[k] = que[maxIndex];
        que[maxIndex] = temp;
    }


}
